package it.unical.canonaco.rende.igpe.game.cbv.datastructure;

import java.util.Iterator;
import java.util.LinkedList;

/**This class is an implementation of a RED-BLACK TREE. A RED-BLACK TREE is a binary search tree that satisfies all the following properties 
 * (also know as RED-BLACK TREE PROPERTIES): </br>
1 - Every node has a color, that is either red or black; </br>
2 - Every leaf is black; </br>
3 - If a node is red, both children are black; </br>
4 - Every path from a given node down to any descendant leaf contains the same number of black nodes. The number of black nodes on such a path 
(not including the initial node but including leaves) is called the black-height of the node; </br>
5 - The root of the tree is black. </br>
</br>
In this implementation every node has five variables: </br>
1 - <i>node_key</i> is the key value of the node, in particular it's the hash code of the element/elements which will stay on this node; </br>
2 - <i>values</i> is an list which contains the elements with the same node_key (collision elements); </br>
3 - <i>color</i> is the color of the node, it's a boolean, and false means black and true means red; </br>
4 - <i>parent</i> is the pointer to the parent of the node, null value means the node is the root of the tree; </br>
5 - <i>children</i> is an array pointer to the children of the node. </br>

@author Massimo Canonaco*/
public class RBTree<T> implements Iterable<T>{
	
	/**This represents the type of children of node. */
	private static enum ChildrenValue{LEFT(0), RIGHT(1);

		/**It's the index in the children array. */
		private final int index;
	
		/**This constructor initialize the index. */
		private ChildrenValue(final int value){
			index = value;
		}
		
		/**This method returns the opposite index/direction in the array, also known as brother index.
		 * @return An integer which represent the brother index. */
		private int oppositeDirection(){
			if(index == 0)
				return 1;
			return 0;
		}
		
		/**This method returns the opposite direction, also known as brother.
		 * @return A ChildrenValue which represent the brother. */
		private ChildrenValue oppositeDirectionEnum(){
			if(this == ChildrenValue.LEFT)
				return ChildrenValue.RIGHT;
			return ChildrenValue.LEFT;
		}
	};
	
	/**It's the root of the tree. */
	private RBNode<T> root;
	
	/**For the second RBT properties every leaf must be black, so we add a null black leaf for satisfying this rule. </br>
	 * This variable is also useful when a node is deleted. */
	private static GenericRedBlackNode null_black_leaf;//  = new BlackLeaf(-1) ;
	
	
	/**This method add the element to the tree. If the element isn't present, a new node will be created and added then in it. 
	 * If the element is present, the element will be added into the <i>values</i> list of the existing node. 
	 * <b>Every node is chosen with the node_key of the element hash code</b>.
	 * @param element is the element to insert into the tree.
	 * @return True, the element wasn't present into the tree so we inserted it; false otherwise.*/
	public boolean add(final T element){
	
	UtilityBoolean bool = new UtilityBoolean();
	
	GenericRedBlackNode new_insert_node = addElement(element,bool);
	
	// If new_insert_node is null, that means the element has been inserted into an existing node; 
	// so there aren't conditions which can influence the "RED-BLACK TREE" properties.
	if(new_insert_node != null)
		{
			fixTreeAfterInsertion(new_insert_node);
			root.color = false;  // We color the root, because fixTreeAfterInsertion could set the root color to red.
								 // For the fifth property, the root must be black.
		}
	
	return bool.getBooleanValue();
	}

	/**When a new node is created and added into the tree, this method is called for fixing the RBT properties and for balancing the tree.
	 * @param new_insert_node is the new node which is inserted into the tree. */
	private void fixTreeAfterInsertion(GenericRedBlackNode new_insert_node)
	{
		  // The first and second properties are valid. The fourth properties is also valid, because we added a RED node so the "black-height" isn't changed
		new_insert_node.color = true;  // Color the new node into red and check if there're some invalid properties							 
		
		GenericRedBlackNode grbn = null;
		ChildrenValue new_insert_parent_node_position = null;
		
		while(new_insert_node != root && new_insert_node.parent.color) // while new_insert_node isn't the root and the third property is violated
			{
				new_insert_parent_node_position = whichChild(new_insert_node.parent); // the algorithm is base on which child is the parent of new_insert_node (is he left or right?)
				grbn = new_insert_node.parent.parent.children[new_insert_parent_node_position.oppositeDirection()]; // now grbn is the uncle of new_insert_node
								
								// In this case the uncle is red, so we paint black the parent and the uncle and then the grandparent red
								// (he was black because the children were red). At last the grandparent becomes the new_insert_node for checking
								// RBT properties to upper levels
								if(grbn.color) 
									{
											grbn.color = false; // Make the uncle black
											new_insert_node.parent.color = false; // Make the parent black
											
											grbn.parent.color = true; // Make the grandparent of new_insert_node red
											new_insert_node = grbn.parent; // Now the new_insert_node becomes his grandparent for checking RBT properties to high levels
											
									}
								// Else if the uncle is black we could have two situations 
								else  
									{	// In this case (ZIG-ZAG case) our new_insert_node is a specific child of his parent 
										// (parent node = left ---> right child, parent = right --> left child).
										// For fixing this case we transform it in the other following case:
										// - we set the new_insert_node to his parent; 
										// - rotation on new_insert_node (if the parent is the left child --> left rotation, right rotation otherwise).
										// So we transformed this 'ZIG-ZAG case' in 'ZIG-ZIG case' which is the following case
										if(new_insert_node == new_insert_node.parent.children[new_insert_parent_node_position.oppositeDirection()]) // if new_insert_node is the right child
											{
												new_insert_node = new_insert_node.parent;
												rotation(new_insert_node, new_insert_parent_node_position);
											}
										
										// In this case (ZIG-ZIG case) the parent of new_insert_node is red (so it has a black grandparent).
										// For fixing this case we color the parent black and the grandparent red, then we make a rotation to
										// the grandparent. If the parent of the new_insert_node is the left child we rotate to right, left otherwise
										new_insert_node.parent.color = false;
										new_insert_node.parent.parent.color = true;
										rotation(new_insert_node.parent.parent, new_insert_parent_node_position.oppositeDirectionEnum());
									}												
					}
	}
	
	/**This method insert the passed element into the tree. In particular if there's an existed node with the same node_key value to the element hash code,
	 * the element is added into the value list; otherwise a new node is created (with the node_key equals to the element hash code) and then the element is inserted
	 * to the value list. </br>
	 * Used principle for seeking and for adding nodes is equivalent to the binary search trees, (hash_code > node_key --> right child node, 
	 * hash_code < node_key --> left child node, hash_code == node_key --> insert the element). 
	 * @param element is the element to be added.
	 * @param bool is the UtilityBoolean parameter which we use for saving the result of the add action. Its value is the result of <i>LinkedList.add(Object)</i>.
	 * @return Null the element is added to an existed node; otherwise it returns the new created node where the element is inserted. */
	@SuppressWarnings("unchecked")
	private GenericRedBlackNode addElement(final T element, UtilityBoolean bool){
		
		// If the tree is new, so it doesn't have any elements, the root is null
		if(root == null || root == null_black_leaf)
			{
				if(null_black_leaf == null)
						null_black_leaf = new RBNode<T>(-1);
				
				root = new RBNode<T>(element.hashCode());
				bool.changeValue(root.addElement(element));
				return root;
			}
	
			final int hash_code_element = element.hashCode();
			RBNode<T> grbn = this.root;
			ChildrenValue direction = null;
			boolean cicle = true;
			
			while(cicle)
				{
					// If there's a node with the same node key, then we can add into it
					if(hash_code_element == grbn.node_key)
						{
							bool.changeValue(grbn.addElement(element));
							grbn = null;  // null when there's an existed node with that node_key/hash_code, so the element is added to the value list 
										  // and there isn't a new created node. So there're no conditions which can break the RBT properties and the tree balance
							cicle = false;
						}
					// The next node which has to be controlled is based if hash_code > node_key, or not
					else if(hash_code_element > grbn.node_key)
								direction = ChildrenValue.RIGHT;
					else
								direction = ChildrenValue.LEFT;		
					
					// If in the previous case we've just inserted the element grbn is null, so we don't need to iterate over.
					// If we don't added, grbn isn't null so we need to iterate.
					if(grbn != null)
						{
							// The next node doesn't exist, so we need to create it and add him to the correct child of the actual node
							if(grbn.children[direction.index] == null_black_leaf)
								{
										grbn = grbn.addChildren(hash_code_element, direction);
										bool.changeValue(grbn.addElement(element)); 
										cicle = false;
								}
							else 
								grbn = (RBNode<T>)grbn.children[direction.index];
						}
				}
			
		return grbn;
	}
/*	/** 
//	private GenericRedBlackNode addElement(final T element){
//		if(root == null)
//			{
//				null_black_leaf = new RBNode<T>(-1);
//				root = new RBNode<T>(element.hashCode());
//				root.addElement(element);
//				return root;
//			}
//	
//			final int hash_code_element = element.hashCode();
//			RBNode<T> grbn = this.root;
//			boolean cicle = true;
//			while(cicle)
//				{
//					if(hash_code_element == grbn.node_key)
//						{
//							grbn.addElement(element);
//							grbn = null; // CON NULL VOGLIO INDICARE CHE NON E' STATO AGGIUNTO NESSUN NUOVO NODO, MA E' STATO AGGIUNTO UN ELEMENTO NELLA LISTA values
//										 // QUINDI NON VI SONO CONDIZIONI CHE POSSANO COMPROMETTERE IL BILANCIAMENTO E LE PROPRIETA' DELL'ALBERO ROSSO-NERO
//							cicle = false;
//						}
//					else if(hash_code_element > grbn.node_key)
//						{
//							if(grbn.children[ChildrenValue.RIGHT.index] != null_black_leaf)
//									grbn = (RBNode<T>) grbn.children[ChildrenValue.RIGHT.index];
//							else
//								{
//									grbn = grbn.addChildren(hash_code_element, ChildrenValue.RIGHT);
//									grbn.addElement(element); 
//									cicle = false;
//								}
//						}
//					else
//						{
//							if(grbn.children[ChildrenValue.LEFT.index] != null_black_leaf)
//									grbn = (RBNode<T>) grbn.children[ChildrenValue.LEFT.index];
//							else
//							{
//									grbn = grbn.addChildren(hash_code_element, ChildrenValue.LEFT);
//									grbn.addElement(element); 
//									cicle = false;
//							}
//						}
//				}
//		return grbn;
//	}*/
	
	/**This method searches if the passed element is present into the tree. The used principle for seeking is equivalent to the binary search trees, 
	 * (hash_code > node_key --> right child node, hash_code < node_key --> left child node, hash_code == node_key --> look if the element is present in value list). 
	 * The key for seeking is the hash_code of the element and the node_key of the node.
	 * @param element is the element to be searched into tree.
	 * @return True, the element is present into the tree; false otherwise.
	 *  */
	@SuppressWarnings("unchecked")
	public boolean search(final T element){
		
		// If the tree is null, it means there aren't any elements to be searched. 
		// So we have to return false, because the element isn't present.
		if(root == null || root == null_black_leaf)
			{
					return false;
			}
		
		// The root isn't null, so there're some elements. 
		// We have to found the proper node and look if the element is present into the value list.
		else
			{
				final int hash_code_element = element.hashCode();
				RBNode<T> grbn = root;
				ChildrenValue direction = ChildrenValue.LEFT;
				boolean cycle = true, found = false;
				
				while(cycle)
				{
					// We have just found the proper node.
					// Now we have to search if the element is present in this node.
					if(hash_code_element == grbn.node_key)
						{
								found = grbn.values.contains(element);
								cycle = false;
						}	
					
					// This actual node (grbn) isn't the proper node, 
					// so we have to set the direction for the next child.
					else if(hash_code_element > grbn.node_key)
								direction = ChildrenValue.RIGHT;
					else
								direction = ChildrenValue.LEFT;
				
				// We searched for all the path and we didn't fine the proper node.
				// So we can stop cycling and then return found (false)
				if(grbn == null_black_leaf)
								cycle = false;
				
				// Else we have to keep looking.
				// so we assign to grbn the next proper child, who could be the proper node.
				else
								grbn = (RBNode<T>) grbn.children[direction.index];
				}
				
				return found;
			}
	}
	
	/**Rotation is a local operation in a search tree that preserves in-order traversal key ordering. It switches family relationship between the nodes.
	 * @param grbn is the GenericRedBlackNode on which the rotation will be applied.
	 * @param direction is the direction on which the rotation will be applied.*/
	@SuppressWarnings("unchecked")
	private void rotation(GenericRedBlackNode grbn, final ChildrenValue direction){
		
		// It's the opposite direction of the rotation. 
		// It's necessary for updating family relationship of some nodes
		final int opposite_direction_index = direction.oppositeDirection();
		
		// It's the child of the node, which we're going to apply rotation, in the opposite direction.
		// If we make a left rotation-->it's the right child; left otherwise.
		// In particular, it's the node which is going to be the parent of the node on which we apply the rotation.
		GenericRedBlackNode temp_node = grbn.children[opposite_direction_index];
		
		// We need to change the child on the opposite direction on the node which'll be rotated for preserving the BST property and the key ordering.
		// Then we need to update the parent of this child.
		grbn.children[opposite_direction_index] = temp_node.children[direction.index];
//			if(temp_node.children[direction.index] != null) // SE IL NODO CON CUI SI SCAMBIA HA UN FIGLIO IN DIRECTION
					temp_node.children[direction.index].parent = grbn;
		
		// temp_node is going to be at the position of grbn and grbn will be rotated, so we need to change the parent of temp_node to the parent of grbn
		temp_node.parent = grbn.parent;
		
		//  In this case grbn is the root of the tree, we need to update the tree with the new root (temp_node)
			if(grbn.parent == null) 
					this.root = (RBNode<T>) temp_node;
		// Else, in this case (where grbn isn't the root of the tree) we need to update the proper child of the parent of grbn
			else
				{	
				grbn.parent.children[whichChild(grbn).index] = temp_node;
//					if(grbn == grbn.parent.children[direction.index]) // SE GRBN ERA IL FIGLIO "DIRECTION" DI SUO PADRE BISOGNA AGGIORNARE IL FIGLIO DI DIRECTION DEL PADRE
//							grbn.parent.children[direction.index] = temp_node;
//					else											  // GRBN FIGLIO DELL'ALTRA DIREZIONE
//							grbn.parent.children[opposite_direction_index] = temp_node;
				}	
			
		// At end, we update the grbn position with his new parent (temp_node)
		grbn.parent = temp_node;
		temp_node.children[direction.index] = grbn;
		
	}
	
	/**This method delete the passed element from the tree if it's present into. 
	 * It searches the proper node where the element could be and then calls the remove function of the LinkedList<T> by the passed element.
	 * The proper node is the node which has the node_key value equals to the element hash code.
	 * The UtilityBoolean bool is used for saving if the element is removed or not.
	 * @param element_to_remove is the element to be deleted from the tree.
	 * @param bool is the parameter which we use for saving the result of the deletion of the element. Its value is the result of <i>LinkedList.remove(Object)</i>
	 * @return Null if there isn't node which has the element in it. Otherwise it returns the RBNode which had the element. */
	@SuppressWarnings("unchecked")
	private RBNode<T> deleteElement(final T element_to_remove, UtilityBoolean bool){
		
		RBNode<T> visitor = null;
		
		// If the tree has some elements that means it has some node, so the root isn't null.
		if(root != null && root != null_black_leaf)
			{
					// We must start searching from the root.
					visitor = root;
					final int hash_code = element_to_remove.hashCode();
//					System.out.println("HASH CODE DA ELIMINARE "+hash_code);
					
						// While we didn't reach the proper node and we didn't walk across all the path, we need to visit the next node which could be the proper node
						while(visitor != null_black_leaf && visitor.node_key != hash_code)
							{								
									if(visitor.node_key < hash_code)
											visitor = (RBNode<T>) visitor.children[ChildrenValue.RIGHT.index];
									else
											visitor = (RBNode<T>) visitor.children[ChildrenValue.LEFT.index];
							}
					// And end we need to check if the while cycle ended 
				    // because we found the right node or because there're not any nodes to be considered.
					// If we found the proper node the visitor node isn't the null_black_leaf, because if
					// we found the null_black_leaf thats means we walked across all the path.
					if(visitor != null_black_leaf)
							bool.changeValue(visitor.values.remove(element_to_remove));
			}
		
		return visitor;
	}
	
	/**This method checks the parent-children situation and return the proper child. 
	 *@param actual_node is the parent.
	 *@return If the parent only has one child, it returns this child. 
	 * If the parent has no children, it returns himself.
	 * If the parent has both children (left and right), it returns the lowest in the RIGHT sub-tree or maximum in the LEFT sub-tree node/nephew. 
	 * <i>(If the lowest node in right sub-tree is red or isn't a black leaf, it returns the right node; left otherwise).</i> */
	private static GenericRedBlackNode followingNode(GenericRedBlackNode actual_node){
		GenericRedBlackNode to_be_returned = null_black_leaf;
		
		// In this case the node is a leaf
		if(actual_node.children[ChildrenValue.LEFT.index] == null_black_leaf && actual_node.children[ChildrenValue.RIGHT.index] == null_black_leaf)
			{
					to_be_returned = actual_node;
			}
		
		// In this case the node isn't a leaf and it has only one child which's the left child
		else if(actual_node.children[ChildrenValue.LEFT.index] != null_black_leaf && actual_node.children[ChildrenValue.RIGHT.index] == null_black_leaf)
			{
					to_be_returned = actual_node.children[ChildrenValue.LEFT.index];
			}
		
		// In this case the node isn't a leaf and it has only one child which's the right child
		else if(actual_node.children[ChildrenValue.RIGHT.index] != null_black_leaf && actual_node.children[ChildrenValue.LEFT.index] == null_black_leaf)
			{
					to_be_returned = actual_node.children[ChildrenValue.RIGHT.index];
			}
		
		// In this case the node isn't a leaf and it has two children.
		// So we need to recover it with the minimum node in the right sub-tree.
		// A minimum node is the node with the lowest node_key value, so it does not
		// have a left child.
		else
			{
					// In this case to_be_returned is the lowestNode in the right sub-tree
					 GenericRedBlackNode lowest_right_subtree_node = lowestNode(actual_node.children[ChildrenValue.RIGHT.index]);
					
					// We find the maximum node in the left sub-tree
					 to_be_returned = maximumNode(actual_node.children[ChildrenValue.LEFT.index]);
					
//					System.out.println("MAX "+maximum_left_node.node_key+" ______ "+maximum_left_node.color);
					// In the lowest is red or isn't a leaf we return the right node.
					// So we couldn't need to re-balance the tree, because a deletion of red node doesn't affect the RBT properties
					if((lowest_right_subtree_node.color || lowest_right_subtree_node.children[ChildrenValue.RIGHT.index] != null_black_leaf)){
//						System.out.println("here");
						to_be_returned = lowest_right_subtree_node;

					}
					}
		
	return to_be_returned;
	}
	
	/**This method checks if the passed node (child) is the left child or the right child of his parent. 
	 *@param child is the child node to be checked.
	 *@return Null, if the child doesn't have parent, otherwise ChildrenValue is the proper "child-direction". */
	private static ChildrenValue whichChild(final GenericRedBlackNode child){
		if(child.parent == null)
			return null;
		
		if(child == child.parent.children[ChildrenValue.LEFT.index])
			return ChildrenValue.LEFT;
		
		return ChildrenValue.RIGHT;
	}
	
	/**This method checks the parent-children situation and return the proper child. 
	 * It's a little bit different from <i>GenericRedBlackNode followingNode(GenericRedBlackNode actual_node)</i>.
	 * @param actual_node is the parent.
	 * @return If the parent only has one child, it returns this child. 
	 * If the parent has no children, it returns the <i><b>null_black_leaf</b></i> .
	 * If the parent has both children (left and right), it returns the a particular node/nephew 
 	<i>(If the lowest node in right sub-tree is red or isn't a black leaf, it returns the right node; left otherwise).</i> */
	private static GenericRedBlackNode nextChild(final GenericRedBlackNode actual_node){
		return followingNode(actual_node) != actual_node ? followingNode(actual_node) : null_black_leaf;
	}

	/** */
	//TODO: eliminare
	@SuppressWarnings("unused")
	private static void expelNode(GenericRedBlackNode to_be_expel, GenericRedBlackNode substitute){
		
	substitute.parent = to_be_expel.parent;
	
	if(to_be_expel.parent != null) // If the node wasn't the root, we need to 'update' his parent
				to_be_expel.parent.children[whichChild(to_be_expel).index] = substitute;

//	to_be_expel.parent = null;
//	to_be_expel.children[0] = null;
//	to_be_expel.children[1] = null;
//	to_be_expel.children = null;

	}
	
	/**This method delete an element, if it's present, from the tree. 
	 * Then if the node, where the element was, has an empty values list, it deletes the node.
	 * When a node is deleted, then the tree is balanced again.
	 * @param element_to_remove is the element to be deleted.
	 * @return True if the element was present into the tree, so we could delete it; false otherwise.*/
	@SuppressWarnings("unchecked")
	public boolean delete(final T element_to_remove){
		
		UtilityBoolean bool = new UtilityBoolean();
		RBNode<T> element_node = deleteElement(element_to_remove,bool);
		
		// If there's no nodes which contain the passed element, it's equal to null_black_leaf.
		// In this case the element node isn't null_black_leaf, that means we deleted the element,
		// so we check if the node isn't empty. A node is empty when is values list is empty.
		// An empty node must be deleted from the tree.
		if(element_node != null_black_leaf && element_node.values.isEmpty())
		{
			// When need to find a substitute for the 'deleted' node.
			// This substitute is called new_node and it's the followingNode.
			// After we found the substitute we need to find a substitute for
			// 'substitute node', and it's the new_node_child which is the nextChild.
			RBNode<T> new_node = (RBNode<T>) followingNode(element_node),
					  new_node_child = (RBNode<T>) nextChild(new_node);
			
			// The empty node will not delete, but it will take the node_key and values list of his substitute.
			// In truth the substitute will be deleted from the tree, so we need to expel it.
			// The first step is to set the parent of his substitute to the parent of the new_node.
			new_node_child.parent = new_node.parent;
			
			// After we updated the parent of the new_node_child, we need to check if the new_node is the root or not.
			// If the new_node is the root we set the root tree to new_node_child, so we update the root.
			if(new_node.parent == null) 
						root = new_node_child;
			
			// Else if the new_node isn't the root, we need to update the proper child of his parent.
			else
						new_node.parent.children[whichChild(new_node).index] = new_node_child;
			
			// If the substitute of the element_node isn't itself, 
			// we must set the values list and the node_key of the element node to the substitute node.
			if(new_node != element_node)
			{
						element_node.node_key = new_node.node_key;
						element_node.values = new_node.values;
			}
			
			// If the substitute is black, the fourth RBT property is compromise.
			// So we must fix the tree by re-balancing the tree and restoring the RBT properties.
			if(!new_node.color)
				{
						fixTreeAfterDelete(new_node_child);
						root.color = false;
//						fixTreeAfterDelete(new_node_child, root);
				}
			
		}
		
		return bool.getBooleanValue();
	}
	
	/** */
	public T getFirst(){
		T first_element = null;
		
		if (root != null && root != null_black_leaf){
			first_element = root.values.getFirst();
		}
		
		return first_element;
	}
	
/*	/** 
//	private void fixTreeAfterDelete(GenericRedBlackNode node, GenericRedBlackNode root){
	private void fixTreeAfterDelete(GenericRedBlackNode node){
		
		GenericRedBlackNode brother = null;
		
		while(node != root && !node.color){
			if(node == node.parent.children[ChildrenValue.LEFT.index])
			{
				brother = node.parent.children[ChildrenValue.RIGHT.index];
				
				// IN QUESTO CASO IL FRATELLO E' DI COLORE ROSSO ---> FIGLI DI COLORE NERO
				if(brother.color) 
				{
					brother.color = node.parent.color; // IL fratello prende il colore del padre
					node.parent.color = true; // il padre (che doveva essere per forza nero, diventa rosso)
					rotation(node.parent, ChildrenValue.LEFT);
					brother = node.parent.children[ChildrenValue.RIGHT.index]; // dopo la rotazione il fratello cambia, e quindi dobbiamo aggiornarlo
				}
				
				// IN QUESTO CASO IL FRATELLO E' DI COLORE NERO E HA ENTRAMBI I FIGLI NERI
				else if (!brother.children[ChildrenValue.LEFT.index].color && !brother.children[ChildrenValue.RIGHT.index].color) {
					brother.color = true;
					if(node.parent.color){
						node.parent.color = false;
						node = root;
					}
					else
					node = node.parent;
				}
				
				// IN QUESTO CASO IL FRATELLO E' DI COLORE NERO E HA UN FIGLIO SINISTRO DI COLORE ROSSO (trasformiamo questo nel caso sia il figlio destro )
				else if(!brother.children[ChildrenValue.RIGHT.index].color){
					brother.children[ChildrenValue.LEFT.index].color = false;
					brother.color = true;
					rotation(brother, ChildrenValue.RIGHT);
					brother = brother.parent;
				}
				else{
				// IN QUESTO CASO IL FRATELLO E' DI COLORE NERO E HA IL FIGLIO DESTRO DI COLORE ROSSO (l'altro puo' essere di qualsiasi colore)
				brother.color = node.parent.color;
				node.parent.color = false;
				brother.children[ChildrenValue.RIGHT.index].color = false;

				rotation(node.parent, ChildrenValue.LEFT);
				node = root;
				}
				
			}
			else
			{
				brother = node.parent.children[ChildrenValue.LEFT.index];
				
				if(brother.color) 
				{
					brother.color = node.parent.color; // IL fratello prende il colore del padre
					node.parent.color = true; // il padre (che doveva essere per forza nero, diventa rosso)
					rotation(node.parent, ChildrenValue.RIGHT);
					brother = node.parent.children[ChildrenValue.LEFT.index]; // dopo la rotazione il fratello cambia, e quindi dobbiamo aggiornarlo
				}
				
				else if (!brother.children[ChildrenValue.LEFT.index].color && !brother.children[ChildrenValue.RIGHT.index].color) {
					brother.color = true;
					
					if(node.parent.color){
						node.parent.color = false;
						node = root;
					}
					else
					node = node.parent;
				}
				else if(!brother.children[ChildrenValue.LEFT.index].color){
					brother.children[ChildrenValue.RIGHT.index].color = false;
					brother.color = true;
					rotation(brother, ChildrenValue.LEFT);
					brother = brother.parent;
				}
				else{
					brother.color = node.parent.color;
					node.parent.color = false;
					brother.children[ChildrenValue.LEFT.index].color = false;
//					brother.children[ChildrenValue.RIGHT.index].color = false; // nel caso sia rosso dobbiamo farlo passare nero
					
					rotation(node.parent, ChildrenValue.RIGHT);
					node = root;
				}
			}
		}
		node.color = false;
	}
*/

/**When a node is deleted, the RBT properties could be compromised. So we need to restore them. This method restore the RBT properties from the passed node.
 * @param node is the node on which we start to check and to restore the RBT properties. */
private void fixTreeAfterDelete(GenericRedBlackNode node){
		
		// The algorithm is based on the brother's cases, so a pointer to the brother is for a quicker algorithm
		GenericRedBlackNode brother = null;
		// Another part of the algorithm is based about the child-position of the passed node.
		// So we need to know what's the child direction of the passed node.
		// We use this variable (direction) for this scope.
		ChildrenValue direction = null;

		// While we don't reach the root and the substitute is black (also know as 'double-black node'),
		// We need to re-color and re-structure.
		while(node != root && !node.color){
				
				// We set the direction to the 'child-position' of node.
				// Now we know if our node is a left or a right child, and which is the position of his brother.
				direction = whichChild(node);
				
				// Our node is the 'direction' position in the parent's array.
				// So his brother is the opposite direction.
				brother = node.parent.children[direction.oppositeDirection()];
				
				// In this case the brother is red, so his children and his parent are black (double red nodes mean wrong tree, look the third RBT property).
				// We fix this case with a rotation on the parent node.
				// We color the brother with the his parent's color (black), then this parent is colored red.
				// We rotate the parent on the direction of our child-node position, then we update the brother.
				// The result is we transformed this case in one of the following cases.
				if(brother.color) 
				{
					brother.color = node.parent.color; // The brother has the same color of his parent
					node.parent.color = true; // The parent is red now
					rotation(node.parent, direction); // Rotation on the parent
					
					brother = node.parent.children[direction.oppositeDirection()]; // After the rotation our node has a new brother, so we update the brother with the new one
				}
				
				// IN QUESTO CASO IL FRATELLO E' DI COLORE NERO E HA ENTRAMBI I FIGLI NERI
				// In this case the brother is black (if he was red, the previous case make him black) and he has two black children.
				// So we make the brother red and the we have two cases:
				// 1 - If his parent his red, we paint him black and then we end because we've just eliminated the the double-black node;
				// 2 - The parent his black, so we need to propagate the re-balancing to upper levels.
//				else if (!brother.children[ChildrenValue.LEFT.index].color && !brother.children[ChildrenValue.RIGHT.index].color) {
				if(!brother.children[ChildrenValue.LEFT.index].color && !brother.children[ChildrenValue.RIGHT.index].color) {
					brother.color = true;
					
					if(node.parent.color)
						{
								node.parent.color = false;
								node = root;
						}
					else
								node = node.parent;
				}
				
				// IN QUESTO CASO IL FRATELLO E' DI COLORE NERO E HA UN FIGLIO SINISTRO DI COLORE ROSSO (trasformiamo questo nel caso sia il figlio destro )
				// In this case the brother has a red child in 'direction'. We check this case if the brother of this child is black.
				// We transform this case in the following case by painting black the 'direction' child  and the brother of the node becomes red.
				// Then we apply a rotation on the brother to the brother  of the (ex) red 'direction' child. 
				// After the rotation we must update the brother.
				// ('direction' child = brother.children[direction])
				else if(!brother.children[direction.oppositeDirection()].color){
					brother.children[direction.index].color = false;
					brother.color = true;
					rotation(brother, direction.oppositeDirectionEnum());
					brother = brother.parent;
				}
				else{
				// IN QUESTO CASO IL FRATELLO E' DI COLORE NERO E HA IL FIGLIO DESTRO DI COLORE ROSSO (l'altro puo' essere di qualsiasi colore)
				// In this case the brother's 'opposite direction' child is red (the other could be either black or red).
				// We fix this case recoloring the brother by his parent's color and the 'opposite direction' child by black.
				// Then we color the node's parent black and the we appy a rotation to the opposite direction of our node on the node's parent.
				// We have just deleted the double-blackness and we can set the node = root for breaking the while condition.
				brother.color = node.parent.color;
				node.parent.color = false;
				brother.children[direction.oppositeDirection()].color = false;

				rotation(node.parent, direction);
				node = root;
				}
			}
		
		node.color = false;
}
	
/** */
public RBNode<T> getRoot(){
	return root;
}

/** */
@SuppressWarnings("unchecked")
public LinkedList<T> getAllElements(){
	
	LinkedList<T> elements_list = new LinkedList<T>();
	if(root != null && root != null_black_leaf)
	{
		LinkedList<RBNode<T>> unvisited_nodes = new LinkedList<RBNode<T>>();
		unvisited_nodes.add(root);
		RBNode<T> visitor = null;
	
	while(!unvisited_nodes.isEmpty()){
		
		visitor = unvisited_nodes.pop();

		for (T element : visitor.values) {
			elements_list.add(element);
		}
		
		if(visitor.children[ChildrenValue.LEFT.index] != null_black_leaf)
			unvisited_nodes.addLast((RBNode<T>) visitor.children[ChildrenValue.LEFT.index]);
		
		if(visitor.children[ChildrenValue.RIGHT.index] != null_black_leaf)
			unvisited_nodes.addLast((RBNode<T>) visitor.children[ChildrenValue.RIGHT.index]);
		
	}
	}
	return elements_list;
}

/**This method searches the lowest node starting from the passed root. The lowest node doesn't have left child.
 * @param root is the node from the algorithm starts his research.
 * @return The node with the lowest node_key value into the tree, starting from root. If the root is the lowest node, this method returns the root. 
 * If the root is null or it's the <i>null_black_leaf</i>, this method returns <i>null_black_leaf</i>.*/
private static GenericRedBlackNode lowestNode(final GenericRedBlackNode root){
		if(root != null && root != null_black_leaf)
			{
					GenericRedBlackNode visitor = root;
		
					while(visitor.children[ChildrenValue.LEFT.index] != null_black_leaf)
							visitor = visitor.children[ChildrenValue.LEFT.index];
			
					return visitor;
		}
		
		return null_black_leaf;
	}
	
/**This method searches the maximum node starting from the passed root. The maximum node doesn't have right child.
 * @param root is the node from the algorithm starts his research. 
 * @return The node with the highest node_key value into the tree, starting from root. If the root is the hightes node, this method returns the root.
 * If the root is null or it's the <i>null_black_leaf</i>, this method returns <i>null_black_leaf</i>.*/
private static GenericRedBlackNode maximumNode(final GenericRedBlackNode root){
	
	if(root != null && root != null_black_leaf)
		{
				GenericRedBlackNode visitor = root;
			
				while(visitor.children[ChildrenValue.RIGHT.index] != null_black_leaf)
						visitor = visitor.children[ChildrenValue.RIGHT.index];
			
				return visitor;
		}
	
	return null_black_leaf;
	}
	
/**This is the concrete representation of the nodes into the Red-Black Tree.*/
private static class RBNode<T> extends GenericRedBlackNode{
		
	/**The elements which have the same hash code to the node_key are inserted into this list, if they're not present yet.
	 * This list'll be only initialized when the first element is inserted. */
	private LinkedList<T> values;
		
	/**This constructor creates and initializes a new RBNode.
	 *  values is still null and the node's children are pointed to the null_black_leaf.
	 *  This constructors at the start calls the constructor of the superior (father) class. 
	 *  @param key is the node_key value.*/
	private RBNode(final int key){
		super(key);
		
		values = null;
		
		// Children are null_black_leaf, so we don't violate the second RBT property
		children[0] = RBTree.null_black_leaf;
		children[1] = RBTree.null_black_leaf;
			
		}
		
		/**This method adds new child node to the node at the passed position/direction.
		 * This method doesn't add any elements to the new node/child.
		 * @param hash_key is the node_key value for the new node.
		 * @param direction is the position in the array children.
		 * @return The new created/added child node.*/
		@SuppressWarnings("unchecked")
		private RBNode<T> addChildren(final int hash_key, final ChildrenValue direction){
//			if(children == null)
//					children = new GenericRedBlackNode[2];
//			
//			if(children[direction.index] == null)
//				{
					children[direction.index] = new RBNode<T>(hash_key);
					children[direction.index].parent = this;
//					children[direction.oppositeDirection()] = RBTree.null_black_leaf; 
//				}
			
			return (RBNode<T>) children[direction.index];
		}
		
		/**This method insert the passed element, if it' not present, into the values list of the node.
		 * In particular the element will be inserted as last.
		 * @param element is the element which will instert into the values list.
		 * @return True, the element wasn't present so the method added its; false otherwise.*/
		private boolean addElement(final T element){
			// The LinkedList values isn't initialized when the node is created.
			// So we need to check if it's null first.
			// If this null, we create a new LinkedList for values and the we add the element.
			if(values == null)
				{
					values = new LinkedList<T>();
					values.add(element);
					return true;
				}
			
			// Else if the values list isn't null, thats means it has some elements.
			// So we need to check if the element is present or not.
			// If it isn't present we add it as last element.
			else if(!values.contains(element))
				{
					values.addLast(element);
					return true;
				}
			
			return false;
		}
	}
	
//	/** */
//	private static class BlackLeaf extends GenericRedBlackNode{
//		
//		/** */
//		private BlackLeaf(final int key){
//			super(key);
//			children[0] = this;
//			children[1] = this;
//
//		}
//	}
	/**This is the abrstraction of the node into the Red-Black Tree. 
	 * This division beetwen generic and concrete nodes is made, for avoiding the java errors when we instantiate new 'generic/template' attributes. */
	private static abstract class GenericRedBlackNode{
		
		/**This represents the color of the node. Legend: <b>false</b> means black, <true> means red.*/
		protected boolean color;
		
		/**It's the value of the node.*/
		protected int node_key;
		
		/**It's an pointer array to the children of this node.*/
		protected GenericRedBlackNode[] children;
		
		/**It's a pointer to the parent of this node.*/
		protected GenericRedBlackNode parent;
		
		/**It's the constructor which assing the key value to the node_key value. 
		 * It colors also the node black and instantiates the children array.
		 * @param key is the value for the node_key.*/
		protected GenericRedBlackNode(final int key){
			node_key = key;
			color = false;
			children = new GenericRedBlackNode[2];
		}
		
		}

	//TODO : commentare
	@Override
	@SuppressWarnings("unchecked")
	public Iterator<T> iterator() {
		return new Iterator<T>() {
			private LinkedList<RBNode<T>> nodes;
			private LinkedList<T> currentValues;
			@Override
			public boolean hasNext() {
				if(nodes == null)
				{
					nodes = new LinkedList<>();
					nodes.addFirst(root);
					System.out.println("init root");
					currentValues = new LinkedList<>();
				}
				return !nodes.isEmpty() || !currentValues.isEmpty();
			}

			@Override
			public T next() {
				if(currentValues.isEmpty())
				{
					
					RBNode<T> node = nodes.removeFirst();
					if(node.children[ChildrenValue.LEFT.index] != null_black_leaf)
						nodes.addLast((RBNode<T>)node.children[ChildrenValue.LEFT.index]);
					if(node.children[ChildrenValue.RIGHT.index] != null_black_leaf)
						nodes.addLast((RBNode<T>)node.children[ChildrenValue.RIGHT.index]);
					
					currentValues = (LinkedList<T>) node.values.clone();
					
				}
				return currentValues.removeFirst();
			}

			@Override
			public void remove() {
				System.out.println("rimuovo "+currentValues.pop());
				currentValues.removeFirst();
			}
		};
	}
}
